package cn.ly.recursion.mergesort;

import cn.ly.util.ArithmeticTool;

public class DArray {
	
	private long[] arr;
	private int nElems;
	public DArray(int size){
		arr = new long[size];
		this.nElems = 0;
	}
	
	public void insert(long value){
		arr[nElems] = value;
		nElems++;
	}
	
	public void display(){
		for(int i=0; i<nElems; i++){
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}
	
	public void mergeSort(){//mergeSort(long[] arr){}
		recMergeSort(this.arr,0,nElems-1);
	}
	
	private void recMergeSort(long[] arr,int lower,int upper){
		if(lower < upper){
			int mid = (lower + upper)/2;//把数组划分成两部分
			recMergeSort(arr,lower,mid);//前一部分继续递归的合并排序
			recMergeSort(arr,mid+1,upper);//后一部分的合并排序
			merge(arr,lower,mid,mid+1,upper);//排序后的数组进行合并
		}
	}
	
	//排序需后的数组进行合并
	private void merge(long[] arr,int lower,int upper,int lower2,int upper2){
		int low = lower;
		int workLength = upper2-lower+1;//计算合并后的数组的长度
		long[] workArr = new long[workLength];//开辟保存合并后新数组的空间
		int j = 0;
		//判断从数组前一部分的起始位置开始主键往后逐个与数组后一部分的每个元素比较，下标++ ，所以条件是不能大于这一部分的最大值下标
		while(lower <= upper && lower2 <= upper2){
			if(arr[lower] < arr[lower2]){//把比较结果中下的放入新数组中，然后把移动了较小数的部分的指针向后++，向后移动一个位置，没有动的指针不变
				workArr[j++] = arr[lower++];
			}else{
				workArr[j++] = arr[lower2++];
			}
		}
		//在比较结束后，有可能有较大的数，剩余在原有数组中，没有插入到新数组中，因为是大的数，所以直接插入即可
		//并且这些数，只可能集中的在数组的前一部分或者后一部分，不可能前后都有
		while(lower <= upper){
			workArr[j++] = arr[lower++];
		}
		while(lower2 <= upper2){
			workArr[j++] = arr[lower2++];
		}
		System.arraycopy(workArr, 0, arr, low, workLength);//low代表了是前一部分的数组的起始位置，还是后一部分的起始位置
		/*for(j=0; j < workLength; j++){
			arr[low+j] = workArr[j];
		}*/

		
		
	}
	
	public static void main(String[] args) {
		DArray arr = new DArray(100);
		for(int i=0; i<10; i++){
			arr.insert(ArithmeticTool.getIntRandom0to100());
		}
		arr.display();
		arr.mergeSort();
		arr.display();
		
	}

}
